\chapter{Complexité}
\section{Séquentiel}
\paragraph{}La complexité de l'algorithme est très simple à analyser dans le cas séquentiel. En effet il s'agit de 4 boucles ``for'' imbriquées :\\
\begin{Verbatim}
//pour chaque ligne de l'image
for(i = matrix.height()/2; i < image.height()-matrix.height()/2; i++)
  //pour chaque element dans la ligne en cours
  for(j = matrix.width()/2; j < image.width()-matrix.width()/2; j++){
    r = 0;
    g = 0;
    b = 0;
    a = 0;

    //pour chaque ligne de la matrice
    for(k = 0; k < matrix.height(); k++)
      //pour chaque element de la ligne de la matrice
      for(l = 0; l < matrix.width(); l++){
        //              coordonnées en Y     coordonnées en X
        r += image[(i-matrix.height()/2)+k][j-matrix.width()/2].r*
             matrix[k][l];
        g += image[(i-matrix.height()/2)+k][j-matrix.width()/2].g*
             matrix[k][l];
        b += image[(i-matrix.height()/2)+k][j-matrix.width()/2].b*
             matrix[k][l];
        a += image[(i-matrix.height()/2)+k][j-matrix.width()/2].a*
             matrix[k][l];
      }

    sortie[(i-matrix.height()/2)+k][j-matrix.width()/2].r = (r > 0)*r;
    sortie[(i-matrix.height()/2)+k][j-matrix.width()/2].g = (g > 0)*g;
    sortie[(i-matrix.height()/2)+k][j-matrix.width()/2].b = (b > 0)*b;
    sortie[(i-matrix.height()/2)+k][j-matrix.width()/2].a = (a > 0)*a;
  }
\end{Verbatim}
\paragraph{}On voit bien que la complexité de l'exécution est linéaire en la taille de l'image et de la matrice. Si on note $w$ la largeur de l'image, $h$ la hauteur et $n$ la dimension de la matrice, la complexité est en $O(h*w*n^2)$.
\section{Parallèle : Processeur}
\paragraph{}La manière de parallèliser le code étant très simple (à savoir : couper l'image sur la hauteur suivant le nombre de threads), la complexité du calcul est très facile à calculer : $O((h*w*n^2)/T)$, avec $h$ la hauteur de l'image, $w$ la largeur, $n$ la dimension de la matrice et $T$ le nombre de coeurs disponibles sur la machine.

\section{Parallèle : GPU}
\paragraph{}Cet algorithme est décomposé en deux parties. La première
est la boucle principale qui va appeller le calcul sur le GPU :\\
\begin{Verbatim}
Lecture de l'image
Découpage de l'image en blocks

Tant qu'il reste des blocks à traiter {
   Copie du block dans la page locked memory
   Complétion du block si nécessaire
   Copie vers la mémoire GPU
   Bind des données dans la mémoire texture
   Appel du kernel //Appel du calcul sur le GPU
}
\end{Verbatim}

\paragraph{}La seconde boucle est celle contenue dans le kernel :\\

\begin{Verbatim}
Copier la matrice de convolution dans la mémoire shared

Faire{
   Pour chaque élément en hauteur du block{
      Pour chaque élément de la matrice{
         Calculer la composate r,g,b,a
         }
      Enregistrer les composantes dans la shared
   }
   Recopier les composantes de la shared dans la mémoire GPU
}Tant que la fin du bloc n'est pas atteinte
\end{Verbatim}

\paragraph{}Complexité de la première boucle : $O(h/(NB\_THREAD*MPS))$
avec $h$ la hauteur de l'image, $NB\_THREAD$ le nombre de threads
souhaité et $MPS$ le nombre de multiprocesseurs sur la carte graphique.\\

\paragraph{}La seconde boucle effectue une triple boucle for :
$O(w*M)$ avec $w$ la largeur de l'image et $M$ la taille de la matrice
de convolution.\\

La compléxité de ce code est donc : $O( \lceil
( \frac{h}{NB\_THREAD*MPS}) \rceil *(w*M))$.
